Reverse words in a string II

Time: O(N); Space:O(1); medium

Given an input character array, reverse the array word by word.

A word is defined as a sequence of non-space characters.

The input character array does not contain leading or trailing spaces and the words are always separated by a single space.

Example 1:

Input: s = “the sky is blue”

Output: “blue is sky the”

Example 2:

Input: s = “a b c”

Output: “c b a”

Challenge: 1. Could you do it in-place without allocating extra space?

[26]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def reverseWords(self, s):
        """
        :type s: a list of 1 length strings (List[str])
        :rtype: nothing
        """
        def reverse(s, begin, end):
            for i in range((end - begin) // 2):
                s[begin + i], s[end - 1 - i] = s[end - 1 - i], s[begin + i]

        reverse(s, 0, len(s))

        i = 0
        for j in range(len(s) + 1):
            if j == len(s) or s[j] == ' ':
                reverse(s, i, j)
                i = j + 1

[27]:

sol = Solution1()

s = list("the sky is blue")
sol.reverseWords(s)
assert "".join(s) == "blue is sky the"

s = list("a b c")
sol.reverseWords(s)
assert "".join(s) == "c b a"

[28]:

class Solution2(object):
    """
    Time: O(N)
    Space: O(N)
    """
    def reverseWords(self, s):
        """
        :type s: a list of 1 length strings (List[str])
        :rtype: nothing
        """
        # first split the string into words
        words = s.split(' ')

        # then reverse the split string list and join using space
        reverse_sentence = ' '.join(reversed(words))

        # finally return the joined string
        return reverse_sentence

[29]:

sol = Solution2()

s = "the sky is blue"
assert sol.reverseWords(s) == "blue is sky the"

s = "a b c"
assert sol.reverseWords(s) == "c b a"